package com.mj.listen2._02_并查集;

/**
 * Quick Union - 基于rank的优化 - 路径减半(Path Halving)
 */
public class UnionFind_QU_R_PH extends UnionFind_QU_R {
    public UnionFind_QU_R_PH(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 让当前v直接指向对应的祖父节点
        while (v != parents[v]) {
            // 找出父节点
            int parent = parents[v];
            // 让当前v的父节点为祖父节点
            parents[v] = parents[parent];
            // 最新的parents[v]再继续往上循环迭代
            v = parents[v];
        }
        return v;
    }
}
